package mo.tags.stack;

public class L1130 {

    public int mctFromLeafValues(int[] arr) {
        int n = arr.length;
        int[][] max = new int[n][n];
        for (int i = 0; i < n; i++) {
            int maxValue = arr[i];
            for (int j = i; j >= 0; j--) {
                maxValue = Math.max(maxValue, arr[j]);
                max[j][i] = maxValue;
            }
        }

        int[][] dp = new int[n][n];
        for (int j = 0; j < n; j++) {
            for (int i = j; i >= 0; i--) {
                int min = Integer.MAX_VALUE;
                for (int k = i; k+1 <= j; k++) {
                    min = Math.min(min, dp[i][k]+dp[k+1][j]+max[i][k]*max[k+1][j]);
                    dp[i][j] = min;
                }
            }
        }
        return dp[0][n-1];
    }

}
